//
// Created by liushuai on 2021/1/21.
//

#include "findMaxForm.h"

int countNum(string &a, char value) {
    int count = 0;
    for (auto elem:a) {
        if (elem == value)
            count += 1;
    }
    return count;
}

int findMaxForm(vector<string> &strs, int m, int n) {
    int str_nums = strs.size();
    vector<int> rows(n+1, 0);
    vector<vector<int>> cols(m+1, rows);
    vector<vector<vector<int>>> DP(str_nums+1, cols);

    for (int index = 1; index <= str_nums; index++) {
        int ones_nums = countNum(strs[index-1], '1');
        int zeros_nums = countNum(strs[index-1], '0');
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (zeros_nums > i || ones_nums > j)
                    DP[index][i][j] = DP[index - 1][i][j];
                else {
                    DP[index][i][j] = max(DP[index - 1][i - zeros_nums][j - ones_nums] + 1, DP[index - 1][i][j]);
                }


            }
        }
    }
    return DP[str_nums][m][n];
}